{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse Linked List II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseBetween"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #反转链表 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你单链表的头指针 <code>head</code> 和两个整数 <code>left</code> 和 <code>right</code> ，其中 <code>left <= right</code> 。请你反转从位置 <code>left</code> 到位置 <code>right</code> 的链表节点，返回 <strong>反转后的链表</strong> 。\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/rev2ex2.jpg\" style=\"width: 542px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5], left = 2, right = 4\n",
    "<strong>输出：</strong>[1,4,3,2,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [5], left = 1, right = 1\n",
    "<strong>输出：</strong>[5]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点数目为 <code>n</code></li>\n",
    "\t<li><code>1 <= n <= 500</code></li>\n",
    "\t<li><code>-500 <= Node.val <= 500</code></li>\n",
    "\t<li><code>1 <= left <= right <= n</code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong> 你可以使用一趟扫描完成反转吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-linked-list-ii](https://leetcode.cn/problems/reverse-linked-list-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-linked-list-ii](https://leetcode.cn/problems/reverse-linked-list-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n2\\n4', '[5]\\n1\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        cur, prev = head, None\n",
    "        while left > 1:\n",
    "            prev = cur\n",
    "            cur = cur.next\n",
    "            left, right = left-1, right-1\n",
    "        con, tail = prev, cur\n",
    "\n",
    "        while right:\n",
    "            third = cur.next\n",
    "            cur.next = prev\n",
    "            prev = cur\n",
    "            cur = third\n",
    "            right -= 1\n",
    "        \n",
    "        if con:\n",
    "            con.next = prev\n",
    "        else:\n",
    "            head = prev\n",
    "        tail.next = cur\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: 'ListNode', m: 'int', n: 'int') -> 'ListNode':\n",
    "        count_m = 0\n",
    "        count_n = 0 \n",
    "        rev = None\n",
    "        result_head = ListNode(0)\n",
    "        result_head.next = head\n",
    "        \n",
    "        while count_m < m - 1:\n",
    "            count_m += 1\n",
    "            head = head.next\n",
    "        \n",
    "        while count_n < n - m + 1:\n",
    "            count_n += 1\n",
    "            rev, rev.next, head = head, rev, head.next\n",
    "        if m == 1:\n",
    "            tmp = result_head\n",
    "        else:\n",
    "            tmp = result_head.next\n",
    "        while count_m > 1:\n",
    "            count_m -= 1\n",
    "            tmp = tmp.next\n",
    "        tmp.next = rev\n",
    "        \n",
    "        while count_n > 0:\n",
    "            count_n -= 1\n",
    "            tmp = tmp.next\n",
    "        tmp.next = head\n",
    "        \n",
    "        return result_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head, m, n):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type m: int\n",
    "        :type n: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return None\n",
    "        # create a dummy node to mark the head of this list\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        \n",
    "        # make a pointer pre as a marker for the node before reversing\n",
    "        pre = dummy\n",
    "        for i in range(m-1):\n",
    "            pre = pre.next\n",
    "            # i += 1\n",
    "        # a pointer to the beginning of a sub-list that will be reversed\n",
    "        start = pre.next\n",
    "        # a pointer to a node that will be reversed\n",
    "        then = start.next\n",
    "        \n",
    "        for j in range(n-m):\n",
    "            start.next = then.next\n",
    "            then.next = pre.next\n",
    "            pre.next = then\n",
    "            then = start.next\n",
    "            \n",
    "        return dummy.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "        def reverseBetween(self, head, m, n):\n",
    "            \"\"\"\n",
    "            :type head: ListNode\n",
    "            :type m: int\n",
    "            :type n: int\n",
    "            :rtype: ListNode\n",
    "            \"\"\"\n",
    "            if not head or m == n: \n",
    "                return head\n",
    "            p = dummy = ListNode(0)\n",
    "            dummy.next = head\n",
    "            for i in range(m-1): \n",
    "                p = p.next\n",
    "                print(p.val)\n",
    "            tail = p.next\n",
    "            print(tail.val)\n",
    "\n",
    "            for i in range(n-m):  #是的应给记住\n",
    "                tmp = p.next                  \n",
    "                p.next = tail.next            \n",
    "                tail.next = tail.next.next    \n",
    "                p.next.next = tmp            \n",
    "            return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    \n",
    "    \n",
    "    def reverseBetween(self, head, m, n):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type m: int\n",
    "        :type n: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if m == n:\n",
    "            return head\n",
    "\n",
    "        dummyNode = ListNode(0)\n",
    "        dummyNode.next = head\n",
    "        pre = dummyNode\n",
    "\n",
    "        for i in range(m - 1):\n",
    "            pre = pre.next\n",
    "        \n",
    "        # reverse the [m, n] nodes\n",
    "        cur = pre.next\n",
    "        for i in range(n - m):\n",
    "            next = cur.next\n",
    "            cur.next = next.next\n",
    "            next.next = pre.next\n",
    "            pre.next = next\n",
    "\n",
    "        return dummyNode.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head, m, n):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type m: int\n",
    "        :type n: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        pre = ListNode(0)\n",
    "        last = pre\n",
    "        if head is None:\n",
    "            return None\n",
    "        for i in range(m - 1):\n",
    "            temp = last.next\n",
    "            last.next = head\n",
    "            head = head.next\n",
    "            last.next.next = temp\n",
    "            last = last.next\n",
    "        right = head\n",
    "        for j in range(n - m + 1):\n",
    "            temp = last.next\n",
    "            last.next = head\n",
    "            head = head.next\n",
    "            last.next.next = temp    \n",
    "        right.next = head\n",
    "\n",
    "        return pre.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head, m, n):\n",
    "        if m == n:\n",
    "            return head\n",
    "        begin = ListNode(0)\n",
    "        begin.next= head\n",
    "        head = begin\n",
    "        num = 0\n",
    "        last = head\n",
    "        head = head.next\n",
    "        while head:\n",
    "            num += 1\n",
    "            print(num,head.val)\n",
    "            if num == m:\n",
    "                superlast = last\n",
    "                superpoint = head\n",
    "                last = head\n",
    "                head = head.next\n",
    "            elif n > num > m:\n",
    "                head.next,head,last = last,head.next,head \n",
    "            elif num == n:\n",
    "                superpoint.next = head.next\n",
    "                head.next = last\n",
    "                superlast.next = head\n",
    "                break\n",
    "            else:\n",
    "                last = head\n",
    "                head = head.next\n",
    "        head = begin \n",
    "        num = 0\n",
    "        return begin.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        h = ListNode(0)\n",
    "        h.next = head\n",
    "        pre = h\n",
    "        for i in range(m-1):\n",
    "            pre = pre.next\n",
    "        q = pre.next\n",
    "        p = None\n",
    "        for i in range(n-m+1):\n",
    "            t = q.next\n",
    "            q.next = p\n",
    "            p,q = q,t\n",
    "        pre.next.next = q\n",
    "        pre.next = p\n",
    "        return h.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "class ListNode:\r\n",
    "    def __init__(self, x):\r\n",
    "        self.val = x\r\n",
    "        self.next = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\r\n",
    "        if m == n:\r\n",
    "            return head\r\n",
    "        # dummy\r\n",
    "        first = ListNode(0)\r\n",
    "        first.next = head\r\n",
    "\r\n",
    "        mn_before = None\r\n",
    "        mn_after = None\r\n",
    "        mn_end = None\r\n",
    "\r\n",
    "        cur = first\r\n",
    "        pre = None\r\n",
    "        i = 0\r\n",
    "        while i <= n:\r\n",
    "            # print(cur.val)\r\n",
    "            if i < m-1:\r\n",
    "                pre = cur\r\n",
    "                cur = cur.next\r\n",
    "            elif i == m-1:\r\n",
    "                mn_before = cur\r\n",
    "                mn_end = cur.next\r\n",
    "                pre = cur\r\n",
    "                cur = cur.next\r\n",
    "            elif i <= n:\r\n",
    "                tmp = cur.next\r\n",
    "                cur.next = pre\r\n",
    "                pre = cur\r\n",
    "                cur = tmp\r\n",
    "            i+=1\r\n",
    "        mn_before.next = pre\r\n",
    "        mn_end.next = cur\r\n",
    "\r\n",
    "        return first.next\r\n",
    "\r\n",
    "# if __name__ == '__main__':\r\n",
    "#     s = Solution()\r\n",
    "#     head = ListNode(0)\r\n",
    "#     cur = head\r\n",
    "#     for i in range(1, 7):\r\n",
    "#         cur.next = ListNode(i)\r\n",
    "#         cur = cur.next\r\n",
    "\r\n",
    "#     head2 = s.reverseBetween(head,2,4)\r\n",
    "#     print('11111111111111')\r\n",
    "#     while head2:\r\n",
    "#         print(head2.val)\r\n",
    "#         head2 = head2.next\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        new_node = ListNode(0)\n",
    "        new_node.next = head\n",
    "        head = new_node\n",
    "        before = head\n",
    "        for i in range(m - 1):\n",
    "            before = before.next\n",
    "        start = before.next\n",
    "        later = before.next\n",
    "        end = start.next\n",
    "        start.next = None\n",
    "        for i in range(n - m):\n",
    "            temp = end.next\n",
    "            end.next = start\n",
    "            start = end\n",
    "            end = temp\n",
    "        before.next = start\n",
    "        later.next = end\n",
    "        return head.next\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        # if m == n: return head\n",
    "\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        begin = dummy\n",
    "        pos = 0\n",
    "        while pos < m-1:\n",
    "            begin = begin.next\n",
    "            pos += 1\n",
    "        end = first = begin.next\n",
    "        second = first.next\n",
    "        pos += 1\n",
    "        while pos < n:\n",
    "            tmp = second.next\n",
    "            second.next = first\n",
    "            first = second\n",
    "            second = tmp\n",
    "            pos += 1\n",
    "        end.next = second\n",
    "        begin.next = first\n",
    "        return dummy.next\n",
    "\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head, m, n):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type m: int\n",
    "        :type n: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        newhead = ListNode(0)\n",
    "        cur, num = newhead, 1\n",
    "        while num < m:\n",
    "            cur.next = head\n",
    "            head = head.next\n",
    "            cur = cur.next\n",
    "            cur.next = None\n",
    "            num += 1\n",
    "        while num <= n:\n",
    "            p = head\n",
    "            head = head.next\n",
    "            p.next = cur.next\n",
    "            cur.next = p\n",
    "            num += 1\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "        cur.next = head\n",
    "        return newhead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "\n",
    "        p1, p2 = None, head\n",
    "        for i in range(m-1):\n",
    "            p1 = p2\n",
    "            p2 = p2.next\n",
    "            # p1, p2 = p2, p2.next\n",
    "        start = p1\n",
    "        end = p2\n",
    "\n",
    "        for i in range(m-1, n):\n",
    "            p1, p1.next, p2 = p2, p1, p2.next\n",
    "        end.next = p2\n",
    "        if start:\n",
    "            start.next = p1\n",
    "            return head\n",
    "        return p1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy_head = first_tail = ListNode(0)\n",
    "        dummy_head.next = head\n",
    "        while m != 1:\n",
    "            first_tail = first_tail.next\n",
    "            m, n = m - 1, n - 1\n",
    "        \n",
    "        cur = rev_tail = first_tail.next\n",
    "        nxt = cur.next\n",
    "\n",
    "        while n != 1:\n",
    "            temp = nxt.next\n",
    "            nxt.next = cur\n",
    "            cur = nxt\n",
    "            nxt = temp\n",
    "            n -= 1\n",
    "        \n",
    "        first_tail.next = cur\n",
    "        rev_tail.next = nxt\n",
    "        return dummy_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        node = head\n",
    "        prev_1 = None\n",
    "        while m > 1:\n",
    "            prev_1 = node\n",
    "            node = node.next\n",
    "            m -= 1\n",
    "            n -= 1\n",
    "        cur_1 = node\n",
    "        prev_2 = None\n",
    "        while n > 0:\n",
    "            temp = node.next\n",
    "            node.next = prev_2\n",
    "            prev_2 = node\n",
    "            node = temp\n",
    "            n -= 1\n",
    "        cur_1.next = node\n",
    "        if not prev_1:\n",
    "            return prev_2\n",
    "        else:\n",
    "            prev_1.next = prev_2\n",
    "            return head    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummyH = ListNode(-1)\n",
    "        dummyH.next = head\n",
    "        pre = dummyH\n",
    "        for i in range(m-1):\n",
    "            pre = pre.next\n",
    "        start = pre.next\n",
    "        tail = pre.next.next\n",
    "        for i in range(n-m):\n",
    "            nextnode = tail.next\n",
    "            start.next = nextnode\n",
    "            tail.next = pre.next\n",
    "            pre.next = tail\n",
    "            tail = start.next\n",
    "        return dummyH.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if not head:\n",
    "            return\n",
    "        if m == 1:\n",
    "            return self.reverseList(head, n)\n",
    "        else:\n",
    "            head.next = self.reverseBetween(head.next, m - 1, n - 1)\n",
    "        return head\n",
    "\n",
    "    def reverseList(self, head: ListNode, n) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        if not n:\n",
    "            return head\n",
    "        if n == 1:\n",
    "            self.next_normal = head.next\n",
    "            return head\n",
    "        last = self.reverseList(head.next, n - 1)\n",
    "        head.next.next = head\n",
    "        head.next = self.next_normal\n",
    "        return last\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        def reverseList(head,n):\n",
    "            if not head or not head.next: return head\n",
    "            if n==1: return head\n",
    "            cur = reverseList(head.next,n-1)\n",
    "            successor = head.next.next\n",
    "            head.next.next = head\n",
    "            head.next = successor\n",
    "            return cur\n",
    "        \n",
    "        if m==1: return reverseList(head,n)\n",
    "        head.next = self.reverseBetween(head.next,m-1,n-1)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "import copy\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head, m, n):\n",
    "        if m==n:\n",
    "            return head\n",
    "        tmp=head\n",
    "        t1=0\n",
    "        count=1\n",
    "        new=ListNode('*')\n",
    "        while count<m:\n",
    "            t1=head\n",
    "            head=head.next\n",
    "            count+=1\n",
    "        while count<=n:\n",
    "            tt=copy.deepcopy(head)\n",
    "            if count==m:\n",
    "                t2=tt\n",
    "            tt.next=new\n",
    "            new=tt\n",
    "            head=head.next\n",
    "            count+=1\n",
    "        if t1:\n",
    "            t1.next=tt\n",
    "        t2.next=head\n",
    "        if m==1:\n",
    "            return tt\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:\n",
    "        dummy = ListNode(0, head)\n",
    "        prev = dummy\n",
    "        for _ in range(left - 1):\n",
    "            prev = prev.next\n",
    "        cur = prev.next\n",
    "        for _ in range(right - left):\n",
    "            nxt = cur.next\n",
    "            cur.next = nxt.next\n",
    "            nxt.next = prev.next\n",
    "            prev.next = nxt\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "        p0=ListNode(0)\n",
    "        p0.next=head\n",
    "        nn=p0\n",
    "        for _ in range(left-1):\n",
    "            p0=p0.next\n",
    "        pre=None\n",
    "        cur=p0.next\n",
    "        for _ in range(right-left+1):\n",
    "            nxt=cur.next\n",
    "            cur.next=pre\n",
    "            pre=cur\n",
    "            cur=nxt\n",
    "\n",
    "        p0.next.next=cur\n",
    "        p0.next=pre\n",
    "        return nn.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next=head)\n",
    "        p0 = dummy\n",
    "        for _ in range(left-1):\n",
    "            p0 = p0.next\n",
    "        pre = None\n",
    "        cur = p0.next\n",
    "        for _ in range(right - left + 1):\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        p0.next.next = cur\n",
    "        p0.next = pre\n",
    "        return dummy.next\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "        # 先把待反转的区域反转，再拼接起来，需要四个指针\n",
    "        def reverse_linked_list(head:ListNode):\n",
    "            cur = head \n",
    "            pre = None\n",
    "            while cur:\n",
    "                next = cur.next   # 未反转部分的头\n",
    "                cur.next = pre    # 当前节点的下一个指向已经反转的部分\n",
    "                pre = cur         # 记住已经反转部分的头\n",
    "                cur = next\n",
    "\n",
    "        # 虚拟头节点\n",
    "        prehead = ListNode(-1)\n",
    "        prehead.next = head\n",
    "        pre = prehead\n",
    "        # 从虚拟头节点走left-1步，pre到达left的前一个节点\n",
    "        for _ in range(left-1):\n",
    "            pre = pre.next\n",
    "        left_node = pre.next\n",
    "\n",
    "        # 从pre再走right-left+1步，left_node到达right节点\n",
    "        right_node = pre\n",
    "        for _ in range(right-left+1):\n",
    "            right_node = right_node.next\n",
    "\n",
    "        # 截取链表\n",
    "        curr = right_node.next # 反转链表的下一段头节点\n",
    "        pre.next = None        # 第一段结束\n",
    "        right_node.next = None # 第二段结束\n",
    "\n",
    "        # 反转中间一段\n",
    "        reverse_linked_list(left_node)\n",
    "\n",
    "        #接回原来的链表\n",
    "        pre.next = right_node\n",
    "        left_node.next = curr\n",
    "        return prehead.next\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "        def reverseN(head:ListNode,n:int)->ListNode:\n",
    "            global successor\n",
    "            if(n==1):\n",
    "                successor=head.next\n",
    "                return head\n",
    "            last= reverseN(head.next,n-1)\n",
    "            head.next.next=head\n",
    "            head.next=successor\n",
    "            return last\n",
    "        def reverseBT(head:ListNode,m,n)->ListNode:\n",
    "            if m==1:\n",
    "                return reverseN(head,n)\n",
    "            head.next=reverseBT(head.next,m-1,n-1)\n",
    "            return head\n",
    "        return reverseBT(head,left,right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "\n",
    "        \n",
    "        successor = None # 后继节点\n",
    "        # 反转以 head 为起点的 n 个节点，返回新的头节点\n",
    "        def reverseN(head: ListNode, n: int) -> ListNode:\n",
    "            global successor\n",
    "            if n == 1:\n",
    "                # 记录第 n + 1 个节点\n",
    "                successor = head.next\n",
    "                return head\n",
    "            # 以 head.next 为起点，需要反转前 n - 1 个节点\n",
    "            last = reverseN(head.next, n - 1)\n",
    "\n",
    "            head.next.next = head\n",
    "            # 让反转之后的 head 节点和后面的节点连起来\n",
    "            head.next = successor\n",
    "            return last \n",
    "        \n",
    "        # 递归，对head翻转(left, right)也就是对head.next翻转(left-1, right-1)\n",
    "        # 直到left-1==0的时候\n",
    "        if left == 1:\n",
    "            return reverseN(head, right)\n",
    "        head.next = self.reverseBetween(head.next, left-1, right-1)\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "# 如果 left 和 right 的区域很大，恰好是链表的头节点和尾节点时，找到 left 和 right 需要遍历一次，反转它们之间的链表还需要遍历一次，虽然总的时间复杂度为 O(N)，但遍历了链表2次，可不可以只遍历一次呢？答案是可以的。\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "        # 利用虚拟头节点 将头节点的处理方式与其他节点的处理方式统一\n",
    "        # 使用三个指针pre,curr,next 利用一次遍历完成这个过程 每次将next提到pre的后面\n",
    "        dummy_head = ListNode()\n",
    "        dummy_head.next = head\n",
    "        # 找到遍历的起点 即要翻转的链表的起点 即left\n",
    "        pre = dummy_head\n",
    "        for _ in range(left-1):\n",
    "            pre = pre.next\n",
    "        # 翻转链表的起点cur 注意cur指向的节点永远没变 只是其位置变了\n",
    "        cur = pre.next\n",
    "       \n",
    "        # 开始遍历翻转 即逐一将next 提到 pre的后一个位置\n",
    "        for _ in range(right - left):\n",
    "            curnext = cur.next\n",
    "            cur.next = curnext.next\n",
    "            curnext.next = pre.next\n",
    "            pre.next = curnext\n",
    "        return dummy_head.next\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "        p0=dummy=ListNode(next=head)\n",
    "        for _ in range(left-1):\n",
    "            p0=p0.next\n",
    "        pre=None\n",
    "        cur=p0.next\n",
    "        for _ in range(right-left+1):\n",
    "            nxt=cur.next\n",
    "            cur.next=pre\n",
    "            pre=cur\n",
    "            cur=nxt\n",
    "        p0.next.next=cur\n",
    "        p0.next=pre\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "        ''' 思路：反转left到right\n",
    "        1. 找到left的前驱节点（确保存在）\n",
    "        2. 从left 反转到 right\n",
    "\n",
    "        \n",
    "        '''\n",
    "        dummyHead = ListNode(next=head) # 对齐位置，设虚拟节点位置为0，head节点为1\n",
    "\n",
    "        # 找到leftPre\n",
    "        leftPre = dummyHead # 初始位置为0\n",
    "        for _ in range(1, left): # [0,...,left-1]\n",
    "            leftPre = leftPre.next\n",
    "        # print(leftPre.val)\n",
    "        newHead = self.reverse(leftPre.next, right - left + 1)\n",
    "        leftPre.next = newHead\n",
    "        return dummyHead.next\n",
    "\n",
    "    def reverse1(self, head, count) -> tuple:\n",
    "        ''' 反转以head为头节点，到count-1位置的节点，返回新的头节点\n",
    "        新末尾节点为head\n",
    "        新头节点为第count个节点\n",
    "        '''\n",
    "        newTail = head\n",
    "        dummyHead = ListNode(next=head)\n",
    "        tailNext = None\n",
    "        cur = head\n",
    "        for index in range(count):\n",
    "            tailNext = cur.next\n",
    "            dummyHead.next, cur.next, cur = cur, dummyHead.next, cur.next\n",
    "        # 收尾\n",
    "        newTail.next = tailNext\n",
    "        return dummyHead.next\n",
    "\n",
    "    \n",
    "    def reverse(self, head, count) -> tuple:\n",
    "        ''' 反转以head为头节点，到count-1位置的节点，返回新的头节点\n",
    "        新末尾节点为head\n",
    "        新头节点为第count个节点\n",
    "        '''\n",
    "        ''' <-2  3 '''\n",
    "        tail = head\n",
    "        pre, cur = None, head\n",
    "        for _ in range(count):\n",
    "            pre, cur.next, cur  = cur, pre, cur.next\n",
    "        tail.next = cur\n",
    "        return pre\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "        p0 = dummy = ListNode(next=head)\n",
    "        for _ in range(left - 1):\n",
    "            p0 = p0.next\n",
    "\n",
    "        pre = None\n",
    "        cur = p0.next\n",
    "        for _ in range(right - left + 1):\n",
    "            nxt = cur.next\n",
    "            cur.next = pre  # 每次循环只修改一个 next，方便大家理解\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "\n",
    "        # 见视频\n",
    "        p0.next.next = cur\n",
    "        p0.next = pre\n",
    "        return dummy.next\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
